package dp;

public class D230818 {
    // 矩阵的最小路径和
    public int minPathSum (int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1) {
                    // 第一行，路径和 就是 当前数字 + 左边的累计的数字
                    dp[i][j] = matrix[i - 1][j - 1] + dp[i][j - 1];
                } else if (j == 1) {
                    // 第一列，路径和 就是 当前数字 + 上边累计的数字
                    dp[i][j] = matrix[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 当前的数字 + 上边 和 左边累计数字的较小值
                    dp[i][j] = matrix[i - 1][j - 1]
                            + Math.min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }


    // 把数字翻译成字符串
    // 1. 递归
    private int count = 0;
    public int solve (String nums) {
        func(nums, 0);
        return count;
    }
    private void func(String nums, int i) {
        if (i == nums.length()) {
            count++;
            return;
        }

        // 递归
        // 1 个数字编码为字符字母
        Integer num = Integer.valueOf(nums.substring(i, i + 1));
        if (num == 0) {
            // 出现 0
            // 那么这条译码路径 走不通
            // 0 只能作为 第二个数字存在，10 20
            return;
        }
        func(nums, i + 1);


        // 递归 2 个数字编码为字母
        if (i + 1 != nums.length()) {
            num = Integer.valueOf(nums.substring(i, i + 2));
            if (num > 0 && num <= 26) {
                func(nums, i + 2);
            }
        }
    }


    // 2. 动态规划
    public int solve2 (String nums) {
        // 排除0
        if(nums.equals("0"))
            return 0;
        // 排除只有一种可能的 10 和 20
        if(nums == "10" || nums == "20")
            return 1;
        // 当 0 的前面不是 1 或 2 时，无法译码，0 种
        for(int i = 1; i < nums.length(); i++){
            if(nums.charAt(i) == '0')
                if(nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2')
                    return 0;
        }
        int[] dp = new int[nums.length() + 1];
        // 辅助数组初始化为1
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= nums.length(); i++){
            // 在11-19，21-26之间的情况
            if((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) > '0')
                    || (nums.charAt(i - 2) == '2'
                    && nums.charAt(i - 1) > '0' && nums.charAt(i - 1) < '7'))
                dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
}
